1. Field of the Invention
The present invention relates to a method and apparatus for calculating the remainder of a modulo division, and more particularly, to a non-iterative technique for calculating the remainder of a modulo division.
2. Description of the Related Art
Most computer systems require the value modulo n of an integer m, generally written m mod n. M mod n operations are utilized in a number of computer processes, for example, address generating, communication channel load balancing, computer graphics, telephone switching and telephone transmission, packet switching and transmission, and digital message encoding/decoding. Therefore, a routine that accepts integers m and n and produces m mod n is a useful computer tool.
The traditional method of calculating the remainder of modulo division is an iterative algorithm:                               N          D                =                  Q          +                      R            D                                              (        1        )            where                N is the dividend,        D is the divisor,        Q is the quotient,        R is the remainder, and        0≦R<D.        
Assuming Q is an n-bit positive integer, the value of Q can be denoted as a sum of binary positions:                     Q        =                              ∑                          j              =              0                                      n              -              1                                ⁢                                    Q              j                        ·                          2              j                                                          (        2        )            where Qj is the jth bit of Q,Qj={0,1} for all j
The traditional iterative algorithm begins by initializing R to N, i.e., R(n)=N and initializing Qn to 1 since N is a positive integer. Then the traditional algorithm calculates R(j) and Qj for j=(n−1) to j=0 iteratively. The complete algorithm, for dividing an n-bit positive integer N by an n-bit positive integer D resulting in an n-bit positive quotient Q and n-bit positive remainder R, is shown in FIG. 1.
An example of the traditional iterative algorithm is set forth below:
Example 1
Assuming N=25, D=7, and n=325 mod 7=4
step A1:R(3) = 25, Q3 = 1, j = 2step B1:j < 0 ? Nostep C1:Q3 = ? Yesstep D1:R(2) = R(3) − D2J = 25 − (7)(4) = −3step E1:R(2) < 0 ? Yesstep F1:Qj = Q2 = 0step G1:j = j − 1 = 2 − 1 = 1step B2:j < 0 ? Nostep C2:Q2 = 1 ? Nostep H1:R(1) = R(2) + D2J = −3 + (7)(2) = 11step E2:R(1) < 0 ? Nostep I1:Q1 = 1step G2:j = j − 1 = 1 − 1 = 0step B3:j < 0 ? Nostep C3:Q1 = 1 ? Yesstep D2:R(0) = R(1) − D2J = 11 − (7)(1) = 4step E3:R(0) < 0 ? Nostep I2:Q0 = 1step G3:j = j − 1 = 0 − 1 = −1step B4:j < 0 ? Yesstep J1:R = R(−1) = R(0) + (1 − Q0) · D = 4 + (1 − 1)7 = 4
According to the traditional iterative algorithm, as illustrated in FIG. 1 and Example 1, the remainder of 25 mod 7 is correctly computed to be 4.
The traditional iterative algorithm for determining the remainder of modulo division is a general purpose method, in that any two positive integers may be entered for N and D. However, as illustrated in Example 1, the traditional iterative algorithm requires numerous computations due to its iterative nature. For example, if D is an n-bit integer with a value D=2n−1. and n is any positive integer less than or equal to (D−1)2, i.e., n is a 2·n-bit integer at maximum, the traditional iterative method requires 6·n numbers of condition testing, 2·n numbers of multiplications (or shifts) and 2·n additions. Therefore, the total number of operations required is 10·n, excluding any value-assigning operations.